home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3473 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.9 KB  |  50 lines
  1. Newsgroups: comp.lang.c
  2. Path: cwi.nl!dik
  3. From: dik@cwi.nl (Dik T. Winter)
  4. Subject: Re: Matrix Multiplication
  5. Message-ID: <DLwzv9.9wu@cwi.nl>
  6. Sender: news@cwi.nl (The Daily Dross)
  7. Nntp-Posting-Host: chrysant.cwi.nl
  8. Organization: CWI, Amsterdam
  9. References: <1996Jan22.110440@gamma.ntu.ac.sg> <4ecjv4$fn2@tamarack.cs.mtu.edu> <822792812snz@genesis.demon.co.uk>
  10. Date: Sun, 28 Jan 1996 23:28:21 GMT
  11.  
  12.  > >Consider optimizing for cache performance.
  13. [Omitting the initialization]
  14.  > >for ( i = 0; i < N; i++ )
  15.  > >   for ( j = 0; j < N; j++ )
  16.  > >      for ( k = 0; k < N; k++ )
  17.  > >         c[i][j] = c[i][j] + a[i][k]*b[k][j];
  18.  > 
  19.  > Or how about:
  20.  >       double sum = 0.0;
  21. ...
  22.  >       c[i][j] = sum;
  23.  > You compiler might be able to perform that optimisation for itself but
  24.  > aliasing issues may make the analysis difficult.
  25.  
  26. In this case aliasing might make it difficult indeed or even impossible,
  27. and doing it is indeed an improvement.  But the proposed version is *not*
  28. optimal for caching; the optimal way to do it is to make the 'j' loop
  29. innermost:
  30.     for ( i = 0; i < N; i++)
  31.        for (k = 0; k < N; k++)
  32.           for (j = 0; j < N; j++)
  33.              c[i][j] = c[i][j] + a[i][k]*b[k][j];
  34. [and this is also optimal on vector processors].
  35. The reason is that if at some stage c[i][j] (or b[k][j]) has a cache miss
  36. a whole cache line is brought in, and this includes some elements of 'c' and
  37. 'b' that are needed on next steps through the loop.  Putting k innermost
  38. gives the benefit only to 'a'.  (But it will also depend a lot on the
  39. cache replacement strategy used by the processor.)
  40.  
  41. Timings on an SGI with a 100 MHz MIPS R4k (in seconds with N = 1000, 10
  42. multiplications):
  43. i innermost        11.08
  44. k innermost         5.92
  45. k innermost + scalar     4.60
  46. j innermost         2.59
  47. -- 
  48. dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
  49. home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
  50.